package dynProg.solvers;

import java.util.HashSet;

import dynProg.Solver;
public class TopDownSolver implements Solver {
	boolean cache[][] = new boolean[1000][1000];
	
	@Override
	public boolean solve(int[] numbers, int sum) {
		
		int[] numbers1;
		if(numbers.length > 0)
			numbers1 = new int[numbers.length - 1];
		else
			numbers1 = new int[numbers.length];
			
		int sum1 = 0;
		//if sum == 0, then sum - numbers[i] == equal (from the bigger problem)
		if(sum == 0){
			return true;
		}
		//if sum < 0, then numbers[i] from the bigger problem is large than sum.
		else if(sum<0){
			return false;
		}
		//the sum of numbers[i].length == 0, equals the sum when sum = 0.
		else if(sum == 0 && numbers.length == 0)
			return true;
		else if(numbers.length == 0 && sum != 0)
			return false;
		
		for(int i = numbers.length - 1; i >= 0; i--){
			//the new sum.
			sum1 = sum - numbers[i];
			if(cache[i][sum]){
				return true;
			}else{
				//numbers1[j] = numbers[i-1];
			for(int j = 0; j < numbers.length; j++){
				if(j != i){
					if(j > i){
						numbers1[j - 1] = numbers[j];
					}
					else{
						numbers1[j] = numbers[j];
					}
				}
			}
			
				if(solve(numbers1, sum1)){
					cache[i][sum1] = true;
					return true;
				}
			}	
		}
		return false;
	}
	/*
	@Override
	public boolean solve(int[] numbers, int sum) {
		//if sum == 0, then sum - numbers[i] == equal (from the bigger problem)
		if(sum == 0){
			return true;
		}
		//if sum < 0, then numbers[i] from the bigger problem is large than sum.
		else if(sum<0){
			return false;
		}
		//the sum of numbers[i].length == 0, equals the sum when sum = 0.
		else if(sum == 0 && numbers.length == 0)
			return true;
		else if(numbers.length == 0 && sum != 0)
			return false;

			if(cache[numbers[0]][sum]){
				return cache[numbers[0]][sum];
			}else{
				cache[numbers[0]][sum] = doSolve(numbers, sum);
				return cache[numbers[0]][sum];
			}

	}
	public boolean doSolve(int[] numbers, int sum){
		int[] numbers1;
		if(numbers.length > 0)
			numbers1 = new int[numbers.length - 1];
		else
			numbers1 = new int[numbers.length];
			
		int sum1 = 0;

		for(int i = numbers.length - 1; i >= 0; i--){
			//the new sum.
			sum1 = sum - numbers[i];

				//numbers1[j] = numbers[i-1];
			for(int j = 0; j < numbers.length; j++){
				if(j != i){
					if(j > i){
						numbers1[j - 1] = numbers[j];
					}
					else{
						numbers1[j] = numbers[j];
					}
				}
			}
				if(solve(numbers1, sum1)){
					cache[numbers[i]][sum1] = true;
					return true;
					
				}

		}

		return false;
	}*/

}
